package _linklist

import org.junit.Assert
import org.junit.Test

/**
 * 203. 移除链表元素
 * https://leetcode.cn/problems/remove-linked-list-elements/description/
 * https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
 *
 * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 *
 * 输入：head = [1,2,6,3,4,5,6], val = 6
 * 输出：[1,2,3,4,5]
 *
 * 输入：head = [], val = 1
 * 输出：[]
 *
 * 输入：head = [7,7,7,7], val = 7
 * 输出：[]
 */
class leetcode_203 {

    @Test
    fun test_1() {
        // 1  2 3 4 -> 4
        // 1 2 3
        val head = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        val l4 = ListNode(4)
        head.next = l2
        l2.next = l3
        l3.next = l4

        val newHeader: ListNode? = removeElements(head, 4)
        val actual = getActual(newHeader)
        val expected = "1,2,3,"
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        // 1 2 3 4 -> 1
        // 2 3 4
        val head = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        val l4 = ListNode(4)
        head.next = l2
        l2.next = l3
        l3.next = l4

        val newHeader: ListNode? = removeElements(head, 1)
        val actual = getActual(newHeader)
        val expected = "2,3,4,"
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_3() {
        // 1  2 3 4 -> 2
        // 1 3 4
        val l1 = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        val l4 = ListNode(4)
        l1.next = l2
        l2.next = l3
        l3.next = l4

        val newHeader: ListNode? = removeElements(l1, 2)
        val actual = getActual(head = newHeader)
        val expected = "1,3,4,"
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_4() {
        // 1  2 3 4 -> 2
        // 1 3 4
        val l1 = ListNode(1)
        val l2 = ListNode(2)
        val l3 = ListNode(3)
        val l4 = ListNode(4)
        l1.next = l2
        l2.next = l3
        l3.next = l4

        val newHeader: ListNode? = removeElements(l1, 5)
        val actual = getActual(head = newHeader)
        val expected = "1,2,3,4,"
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_5() {
        // 7  7 7 7 -> 7
        // ""
        val l1 = ListNode(7)
        val l2 = ListNode(7)
        val l3 = ListNode(7)
        val l4 = ListNode(7)
        l1.next = l2
        l2.next = l3
        l3.next = l4

        val newHeader: ListNode? = removeElements(l1, 7)
        val actual = getActual(head = newHeader)
        val expected = ""
        Assert.assertEquals(expected, actual)
    }

    private fun getActual(head: ListNode?): String {
        var s: String = ""
        var p: ListNode? = head
        while (null != p) {
            s = s + p.`val` + ","
            p = p.next
        }
        return s
    }

    private class ListNode(var `val`: Int) {
        var next: ListNode? = null
    }

    private fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        return removeElements1(head, `val`)
//        return removeElements2(head, `val`)
    }

    private fun removeElements1(head: ListNode?, `val`: Int): ListNode? {
        // 使用虚拟节点
        // T - N
        // S - 1
        if (null == head) {
            return null
        }
        val dummyHead: ListNode = ListNode(-1)
        dummyHead.next = head
        var left: ListNode? = dummyHead
        var right: ListNode?
        while (left != null) {
            right = left.next
            if (right == null) {
                break
            }
            if (right.`val` == `val`) {
                left.next = right.next
            } else {
                left = right
            }
        }
        return dummyHead.next
    }

    private fun findPrev(dummyHead: ListNode, target: Int): ListNode? {
        var prev: ListNode? = dummyHead;
        while (prev != null) {
            if (prev.next == null) {
                return null
            }
            if (prev.next?.`val` == target) {
                return prev
            }
            prev = prev.next
        }
        return null
    }

    private fun removeElements2(head: ListNode?, `val`: Int): ListNode? {
        // T - N
        // S - 1
        /*
        使用原来链表进行删除操作
        如果head 为 空，则返回 空

        找到新的header。
        如果没有新header，则返回 空

        left = new header
        loop(){
            right = left next
            if(right null){
                stop
            }
            if(right == target){
                remove right
            }
            else{
                left  = right
            }
        }

         */
        if (null == head) {
            return null
        }
        var newHead: ListNode? = null
        var p: ListNode? = head
        while (newHead == null && p != null) {
            if (p.`val` == `val`) {
                p = p.next
                continue
            } else {
                newHead = p
            }
        }
        if (newHead == null) {
            return null
        }
        var left: ListNode? = newHead
        var right: ListNode?
        while (left != null) {
            right = left.next
            if (right == null) {
                break
            }
            if (right.`val` == `val`) {
                left.next = right.next
            } else {
                left = right
            }
        }
        return newHead
    }
}